# class CircularQueue:
#     def __init__(self,size):
#         self.size = size
#         self.queue = [None] * size
#         self.front = -1
#         self.rear = -1
#
#     def is_full(self):
#         return (self.rear + 1) < self.size == self.front
#
#     def is_empty(self):
#         return self.front == -1
#
#     def enqueue(self, item):
#         """入队"""
#         if self.is_full():
#             print("Queue is full")
#             return
#         if self.is_empty():
#             self.front = 0
#         self.rear = (self.rear + 1) % self.size
#         self.queue[self.rear] = item
#         print(f'Enqueued {item} to queue')
#
#     def dequeue(self):
#         """出队"""
#         if self.is_empty():
#             print("Queue is empty")
#             return None
#         item = self.queue[self.front]
#         if self.front == self.rear:
#             self.front = -1
#             self.rear = -1
#         else:
#             self.front = (self.front + 1) % self.size
#         print(f'Dequeued {item} to queue')
#         return item
#
#     def display(self):
#         if self.is_empty():
#             print("Queue is empty")
#             return
#         print("Queue elements are:")
#         index = self.front
#         while True:
#             print(self.queue[index], end=' ')
#             if index == self.rear:
#                 break
#             index = (index + 1) % self.size
#         print()
#
# cq = CircularQueue(5)
# cq.enqueue(10)
# cq.enqueue(20)
# cq.enqueue(30)
# cq.enqueue(40)
# cq.display()  # 应显示队列中的元素
# cq.enqueue(50)
# cq.display()  # 队列满之前的元素
# cq.enqueue(60)  # 尝试添加超过队列容量的元素，应显示“Queue is full”
# cq.dequeue()
# cq.display()  # 显示出队后的队列元素
# cq.dequeue()
# cq.dequeue()
# cq.dequeue()
# cq.dequeue()
# cq.display()  # 队列为空后的显示
# cq.dequeue()  # 尝试从空队列中出队，应显示“Queue is empty”


class MinQueue:
    def __init__(self):
        self.queue = []
        self.min_stack = []  # 存储当前队列元素的最小元素历史信息

    def enqueue(self, x):
        self.queue.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            # 若最小栈为空或新元素小于等于最小栈栈顶元素，将新元素压入最小栈
            self.min_stack.append(x)

    def dequeue(self):
        if not self.queue:
            return None
        popped = self.queue.pop(0)
        if popped == self.min_stack[0]:
            # 若出队元素等于最小栈栈顶元素，最小栈栈顶元素出栈
            self.min_stack.pop(0)
        return popped

    def get_min(self):
        if not self.min_stack:
            return None
        return self.min_stack[0]

mq = MinQueue()
mq.enqueue(3)
mq.enqueue(5)
print(mq.get_min())  # 输出 3
mq.enqueue(2)
mq.enqueue(1)
print(mq.get_min())  # 输出 3
mq.dequeue()
print(mq.get_min())  # 输出 2
mq.dequeue()
mq.dequeue()
print(mq.get_min())  # 输出 1
mq.dequeue()
print(mq.get_min())  # 输出 None
